package com.xiyou.week06.greedy;

/**
 * 45. 跳跃游戏 II
 *
 * @ClassName：Jump
 * @Author：西柚
 * @Date：2022/2/24 3:22 下午
 * @Versiion：1.0
 */
public class Jump {

    /**
     * 输入: nums = [2,3,1,1,4]
     * 输出: 2
     * 解释: 跳到最后一个位置的最小跳跃数是 2。
     * 从下标为 0 跳到下标为 1 的位置，跳1步，然后跳3步到达数组的最后一个位置。
     *
     * @param nums
     * @return
     */
    public int jump(int[] nums) {
        int now = 0;
        int ans = 0;
        while (now < nums.length - 1) {
            int right = now + nums[now];
            // [now + 1, right] 可达范围
            if (right >= nums.length - 1) {
                return ans + 1;
            }
            int nextRight = right;
            int next = now;
            for (int i = now + 1; i <= right; i++) {
                if (i + nums[i] > nextRight) {
                    nextRight = i + nums[i];
                    next = i;
                }
            }
            now = next;
            ans++;
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{2, 3, 1, 1, 4};
        Jump jump = new Jump();
        System.out.println(jump.jump(nums));
    }

}
